class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<string> s(10);
		s[2] = "abc";
		s[3] = "def";
		s[4] = "ghi";
		s[5] = "jkl";
		s[6] = "mno";
		s[7] = "pqrs";
		s[8] = "tuv";
		s[9] = "wxyz";

		vector<string> result;
		calc(s, digits, 0, "", result);
		return result;
	}

	void calc(const vector<string>& s, const string& digits, int depth, string cur, vector<string>& result) {
		if (depth == digits.length()) {
			result.push_back(cur);
			return;
		}
		int c = static_cast<int>(digits[depth] - '0');
		for (int i = 0; i < s[c].length(); ++i) {
			calc(s, digits, depth + 1, cur + s[c][i], result);
		}
	}

};